class Solution {
public:
    //https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fvalid-triangle-number%2F    
    int triangleNumber(vector<int>& nums) 
    {
        int fix = nums.size() - 1;
        sort(nums.begin(), nums.end());//先排序
        int count = 0;
        for(; fix > 1; fix--)
        {
            int left = 0, right = fix - 1;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[fix])//因为是有序的故left右边的数都是大于它的
                {
                    count += right-left;
                    right--;
                }
                else if(nums[left] + nums[right] <= nums[fix])//以上可得下标right左边的数都是小于它
                {
                    left++;
                }
            }
        }
        return count;
    }

    //https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fhe-wei-sde-liang-ge-shu-zi-lcof%2F
    vector<int> twoSum(vector<int>& price, int target) 
    {
        int left = 0, right = price.size() - 1;
        while(left < right)
        {
            if(price[left] + price[right] > target)
            {
                right--;
            }
            else if(price[left] + price[right] < target)
            {
                left++;
            }
            else{
                return {price[left], price[right]};
            }
        }
        return {};
    }

    //https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2F3sum%2F
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        vector<vector<int>> v1;
        sort(nums.begin(), nums.end());
        for(int i = nums.size() - 1; i > 1; i--)
        {
            int left = 0, right = i - 1;
            while(left < right)
            {
                if(nums[left] + nums[right] + nums[i] > 0)
                {
                    right--;
                }
                else if(nums[left] + nums[right] + nums[i] < 0)
                {
                    left++;
                }
                else
                {
                    v1.push_back({nums[left],nums[right],nums[i]});
                    while(left < right && nums[left] == nums[left + 1])
                    {
                        left++;
                    }
                    while(right > left && nums[right] == nums[right - 1])
                    {
                        right--;
                    }
                    left++;//此时下标left的值已经push到vector中，故left++
                    right--;//下表left的值变了，下表为right，left,i的值相加一定不等于0，故为节省时间
                }
            }
            while(i > 1 && nums[i] == nums[i - 1])
            {
                i--;
            }            
        }
        return v1;
    }
};